#include <iostream>
using namespace std;
int main()
{
	int arr[] = { 9,9,1,2,31,43,4,2,8,7,5 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//for (int i = 1; i < sz; i++)
	//{
	//	int j = i - 1;
	//	int target = arr[i];
	//	while (j > -1 && target > arr[j])
	//	{
	//		arr[j + 1] = arr[j];
	//		j--;
	//	}
	//	arr[j + 1] = target;
	//}
	for (int interval = sz / 2; interval > 0; interval /= 2)
	{
		for (int i = interval; i < sz; i++)
		{
			int j = i - interval;
			int target = arr[i];
			while (j > -1 && target > arr[j])
			{
				arr[j + interval] = arr[j];
				j -= interval;
			}
			arr[j + interval] = target;
		}
	}
	for (int i = 0; i < sz; i++)
	{
		cout << arr[i] << "  ";
	}
	system("pause");
	return 0;
}